洛谷题解 UVA11039 【Building designing】

发表于 | 更新于 | 阅读次数：
本文字数： 1.2k | 阅读时长 ≈ 1 分钟

题意简述：

给你一个长度n的序列，选出一个子序列排列出一正一负交替并且绝对值递增使得子序列长度最长，求它的长度。

思路：

首先题目数据量不大，完全可以用扫描的方法过。

首先对得到的序列进行排序（当然要用到万恶的$sort$），将其按绝对值大小从小到大排。

随后，选定绝对值最小的数作为开头，并用一个变量$last$记录。

接着从2开始扫到n：

对于每一个数，若$last<0$且当前数大于0，更新$last$为当前数并将子序列长度+1；

若$last>0$且当前数小于0，更新$last$为当前数并将子序列长度+1；

以上步骤相当于做了一个一正一负逐个选择的过程。

时间复杂度$O(n \ log\ n)$。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int T,n,list[500010],last,ans;

inline int c_abs(int k)
{
	return (k>0)?k:-k;
}

bool cmp(int x,int y)
{
	return c_abs(x)<c_abs(y);
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int a=1;a<=n;++a)
		{
			scanf("%d",&list[a]);
		}
		sort(list+1,list+n+1,cmp);
		last=list[1];
		ans=1;
		for(int a=2;a<=n;a++)
		{
			if(last<0&&list[a]>0)
			{
				last=list[a];
				ans++;
				continue;
			}
			if(last>0&&list[a]<0)
			{
				last=list[a];
				ans++;
				continue;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

题目详见:https://www.luogu.com.cn/problem/UVA11039